package com.lry.basic.algorithm.graph;

import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class DirectedGraph {

    //numCourses：课程数，顶点数
    //prerequisites: 边，右到左
    TreeSet<Integer>[] adj;
    int[]  visited;

    public boolean canFinish(int numCourses, int[][] prerequisites){

        visited = new int[numCourses];

        adj = new TreeSet[numCourses];
        for(int i=0;i<numCourses;i++){
            adj[i] = new TreeSet<>();
        }

        for(int i=0;i<prerequisites.length;i++){
            int a = prerequisites[i][1];
            int b = prerequisites[i][0];
            //有向图
            adj[a].add(b);
        }

        for(int v=0;v<numCourses;v++){
            if(dfs(v)){
                return false;
            }
        }
        return true;
    }


    /**
     * 判断有向图是否有环
     * @param v
     * @return
     */
    private boolean dfs(int v){

        //1代表同一圈中dfs到了自己，则证明有环
        if(visited[v]==1){
            return true;
        }
        if(visited[v]==-1){
            return false;
        }
        visited[v]=1;

        for(int w:adj[v]) {
            if(dfs(w)){
                return true;
            }
        }

        //-1代表从此节点dfs遍历完了没有发现环
        visited[v]=-1;
        return false;
    }

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph();
        System.out.println(graph.canFinish(3,
                new int[][]{{1,0},{2,0},{2,1}}));
    }
}

